package main

import (
	"container/list"
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 使用list包模拟队列
func levelOrder(root *TreeNode) [][]int {

	var res [][]int
	if root == nil {
		return nil
	}
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() != 0 {
		var tempArray []int
		size := queue.Len()
		for i := 0; i < size; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			tempArray = append(tempArray, node.Val)
		}
		res = append(res, tempArray)
	}

	return res
}

// 使用slice模拟队列
func levelOrder2(root *TreeNode) [][]int {
	var res [][]int
	queue := make([]*TreeNode, 0)
	if root == nil {
		return nil
	}
	queue = append(queue, root)
	for len(queue) != 0 {
		var tempArray []int
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			tempArray = append(tempArray, node.Val)
		}
		res = append(res, tempArray)
	}
	return res
}
func main() {
	node1 := &TreeNode{Val: 1}
	node2 := &TreeNode{Val: 2}
	node3 := &TreeNode{Val: 3}
	node4 := &TreeNode{Val: 4}
	node5 := &TreeNode{Val: 5}
	node6 := &TreeNode{Val: 6}
	node7 := &TreeNode{Val: 7}
	node1.Left = node2
	node1.Right = node3

	node2.Left = node4
	node2.Right = node5

	node3.Left = node6
	node3.Right = node7

	res := levelOrder2(node1)
	fmt.Printf("res: %v\n", res)
}
